package leetcode.editor.template.sort;

import java.util.HashMap;

public class HeapSort {

    public static void main(String[] args) {
        new HeapSort().heap_sort();
    }

    int[] arr = new int[]{7, 5, 8, 3, 5};

    // 堆排
    public void heap_sort() {
        build_heap();

        for (int i = arr.length - 1; i > 0; i--) {
            swap(1, i);
            down(i, arr.length - 1);
        }
    }

    // 建堆
    public void build_heap() {
        for (int i = arr.length - 1; i > 0; i--) {
            down(i, arr.length - 1);
        }
    }

    // 移动数组(大顶堆)
    public void down(int x, int end) {
        while (2 * x <= end) {
            int t = 2 * x;
            if (t + 1 < end && arr[t + 1] > arr[t]) t++;
            if (arr[t] <= arr[x]) break;
            swap(x, t);
            x = t;
        }
    }

    public void swap(int i, int j) {
        int t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }


}
